// 解决问题d的程序
// Created by Jisam on 2024/7/27 22:01.
// solve d
#include <bits/stdc++.h>

// 定义各种pair和vector的别名，以及优先队列的别名
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using namespace std;

// 定义常量N，用于表示数组大小的上限
const int N = 1e5 + 5;
// 定义全局变量ans，用于存储答案
i64 ans;

// solve函数用于解决问题
void solve() {
    // 输入问题规模n和查询数量q
    int n, q;
    cin >> n >> q;
    // 输入数组a
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 输入查询的两个参数b和k
    vector<int> b(q), k(q);
    for (int i = 0; i < q; i++) {
        cin >> b[i] >> k[i];
    }
    // 对数组a进行排序，以便后续查询
    sort(a.begin(), a.end());
    // 遍历每个查询，使用二分查找确定满足条件的最小值
    for (int i = 0; i < q; i++) {
        // 初始化二分查找的上下界
        int lo = 0, hi = 1e9;
        // 当上下界不相等时，进行二分查找
        while (lo < hi) {
            // 二分计算 （b[i] - mid , b[i] + mid）的距离
            // 计算中间值
            int x = (lo + hi) >> 1;
            // 计算区间左右边界
            int l = b[i] - x;
            int r = b[i] + x;
            /* 计算区间[l, r]内a中元素的个数 */
            int cnt = upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l);

            if (cnt >= k[i]) {
                hi = x;
            } else {
                // 否则，调整下界
                lo = x + 1;
            }
        }
        // 输出结果
        cout << lo << "\n";
    }
}

// 程序入口
int main() {
    // 关闭同步输入输出，提高效率
    ios::sync_with_stdio(false);
    // 解除cin与cout的绑定，提高输入输出效率
    cin.tie(nullptr);
    // 定义测试用例数量
    int T = 1;
    // while循环执行T次测试用例
    while (T--) solve();
    // 返回0表示程序正常结束
    return 0;
}
